{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TailRecursive annotation\n",
    "\n",
    "Let's check what is the effect of `@TailRecursive` annotation on the simple recursive definition of factorial function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import groovy.transform.CompileStatic\n",
    "import groovy.transform.TailRecursive\n",
    "import groovy.transform.TypeChecked\n",
    "\n",
    "@CompileStatic\n",
    "@TypeChecked\n",
    "class X {\n",
    "    static final BigInteger factorial0(int n) {\n",
    "        (n <= 1) ? 1G : factorial0(n-1).multiply(BigInteger.valueOf(n))\n",
    "    }\n",
    "\n",
    "    static final BigInteger factorial1(int n, BigInteger acc = 1G) {\n",
    "        (n <= 1) ? acc : factorial1(n-1, acc.multiply(BigInteger.valueOf(n)))\n",
    "    }\n",
    "\n",
    "    @TailRecursive\n",
    "    static final BigInteger factorial2(int n, BigInteger acc = 1G) {\n",
    "        (n <= 1) ? acc : factorial2(n-1, acc.multiply(BigInteger.valueOf(n)))\n",
    "    }\n",
    "}\n",
    "\n",
    "x = new X()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Although we can time the execution of the calls, it is not very accurate; such micro benchmarks should be performed in more controlled environment, such us under [JMH](https://openjdk.java.net/projects/code-tools/jmh/).\n",
    "\n",
    "For example, see [blog posts of Szymon Stępniak](https://e.printstacktrace.blog/tail-recursive-methods-in-groovy/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "\n",
    "x.factorial0(19_000).toString().length()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "\n",
    "x.factorial1(19_000).toString().length()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "\n",
    "x.factorial2(19_000).toString().length()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The real difference is the use of stack. Non-tail recursive calls exhaust the stack space at some point, whereas tail recursive calls don't add frames to the stack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "factSize = { n, cl ->\n",
    "    println \"Factorial of ${n} has ${cl(n).toString().length()} digits\"\n",
    "}\n",
    "\n",
    "factSize 2_000, x.&factorial0\n",
    "factSize 2_000, x.&factorial1\n",
    "factSize 2_000, x.&factorial2\n",
    "\n",
    "factSize 100_000, x.&factorial2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "try {\n",
    "    factSize 100_000, x.&factorial1\n",
    "} catch (Throwable e) {\n",
    "    assert e instanceof StackOverflowError\n",
    "    println e\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "jupytext": {
   "encoding": "// -*- coding: utf-8 -*-",
   "formats": "ipynb,groovy:light"
  },
  "kernelspec": {
   "display_name": "Groovy",
   "language": "groovy",
   "name": "groovy"
  },
  "language_info": {
   "codemirror_mode": "groovy",
   "file_extension": ".groovy",
   "mimetype": "",
   "name": "Groovy",
   "nbconverter_exporter": "",
   "version": "2.5.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
